{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7901c252-c4cd-4da5-8da3-5c21eed5e75a",
   "metadata": {},
   "source": [
    "# 冒泡排序"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b81fe749-def6-4a12-a137-1d06ab19ea9f",
   "metadata": {},
   "source": [
    "冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最\n",
    "大值放到正确的位置上。本质上，每个元素通过“冒泡”找到自己所属的位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2a327cc-0140-47ba-b6a3-035904e66860",
   "metadata": {},
   "source": [
    "下图展示了冒泡排序的第一轮遍历过程。深色的是正在比较的元素。如果列表中有 n 个元素，那么第一轮遍历要比较 n–1 对。注意，最大的元素会一直往前挪，直到遍历过程结束。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a4edd41-17e7-4cf0-b9f0-f22ee1d50a67",
   "metadata": {},
   "source": [
    "![冒泡排序](bubble_sort.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "449d9efa-c1f6-41be-b982-39db1ac602f0",
   "metadata": {},
   "source": [
    "第二轮遍历开始时，最大值已经在正确位置上了。还剩 n–1 个元素需要排列，也就是说要比较 n–2 对。既然每一轮都将下一个最大的元素放到正确位置上，那么需要遍历的轮数就是 n–1。\n",
    "完成 n–1 轮后，最小的元素必然在正确位置上，因此不必再做处理。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f8b8e64-d2df-4142-8801-ec6cec24a214",
   "metadata": {},
   "source": [
    "下面给出了完整的bubble_sort 函数。该函数以一个列表为参数，必要时会交换其中的元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "16c76d0a-0d4d-48d7-9663-fcf70c3c6d9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(alist):\n",
    "    for passnum in range(len(alist)-1, 0, -1):\n",
    "        for i in range(passnum):\n",
    "            if alist[i] > alist[i+1]:\n",
    "                temp = alist[i]\n",
    "                alist[i] = alist[i+1]\n",
    "                alist[i+1] = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "88ed47b5-5520-4fed-b694-76edf9a27e1d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before sorting: [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
      "after sorting: [17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "print(f\"before sorting: {a_list}\")\n",
    "bubble_sort(a_list)\n",
    "print(f\"after sorting: {a_list}\")\n",
    "assert a_list == sorted(a_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "e8ecbfb1-757c-4d48-86d0-28dea74a6e9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint, seed\n",
    "seed(13)\n",
    "lst_to_sort = [randint(100, 999) for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "0fd0bd89-5fb4-4b9f-83af-eb7725ae5d1c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17.6 ms ± 190 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit bubble_sort(lst_to_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76d5aff9-4b9a-4366-ad02-94ca441c89e9",
   "metadata": {},
   "source": [
    "在分析冒泡排序算法时要注意，不管一开始元素是如何排列的，给含有 n 个元素的列表排序总需要遍历 n–1 轮。下表展示了每一轮的比较次数。总的比较次数是前 n–1 个整数之和。由于 前 n 个整数之和是 $\\frac{1}{2}n^2+\\frac{1}{2}n$ 因此前 n–1 个整数之和就是 $\\frac{1}{2}n^2+\\frac{1}{2}n-n$ 即 $\\frac{1}{2}n^2-\\frac{1}{2}n$。这表明， 该算法的时间复杂度是 $O(n^2)$ 。在最好情况下，列表已经是有序的，不需要执行交换操作。在最 坏情况下，每一次比较都将导致一次交换。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce343bce-2090-4b36-b36d-e8481ea2a159",
   "metadata": {},
   "source": [
    "| 轮次 | 比较次数 |\n",
    "| ---- | -------- |\n",
    "| 1    | n-1      |\n",
    "| 2    | n-2      |\n",
    "| 3    | n-3      |\n",
    "| ...  | ...      |\n",
    "| n-1  | 1        |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbd957de-8416-4465-bb53-09d77458d09f",
   "metadata": {},
   "source": [
    "冒泡排序通常被认为是效率最低的排序算法，因为在确定最终的位置前必须交换元素。“多余”的交换操作代价很大。不过，由于冒泡排序要遍历列表中未排序的部分，因此它具有其他排\n",
    "序算法没有的用途。特别是，如果在一轮遍历中没有发生元素交换，就可以确定列表已经有序。可以修改冒泡排序函数，使其在遇到这种情况时提前终止。对于只需要遍历几次的列表，冒泡排\n",
    "序可能有优势，因为它能判断出有序列表并终止排序过程。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da041a52-e0be-4663-8d8d-7c4d077b73a3",
   "metadata": {},
   "source": [
    "下面实现了如上所述的修改，这种排序通常被称作**短冒泡**。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "29665877-59ea-4798-bef0-03bcb770c759",
   "metadata": {},
   "outputs": [],
   "source": [
    "def short_bubble_sort(alist):\n",
    "    exchanges = True\n",
    "    passnum = len(alist)-1\n",
    "    while passnum > 0 and exchanges:\n",
    "        exchanges = False\n",
    "        for i in range(passnum):\n",
    "            if alist[i] > alist[i+1]:\n",
    "                exchanges = True\n",
    "                temp = alist[i]\n",
    "                alist[i] = alist[i+1]\n",
    "                alist[i+1] = temp\n",
    "        passnum = passnum - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f931ebba-a632-4d1c-898c-f8e878f08873",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before sorting: [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
      "after sorting: [17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "print(f\"before sorting: {a_list}\")\n",
    "short_bubble_sort(a_list)\n",
    "print(f\"after sorting: {a_list}\")\n",
    "assert a_list == sorted(a_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "4571c8d8-62f3-42ff-bc6c-e2d2943a0790",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint, seed\n",
    "seed(13)\n",
    "lst_to_sort = [randint(100, 999) for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "87a32e6a-ad3f-46a5-953f-9dc5aa3125be",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37.6 μs ± 581 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit short_bubble_sort(lst_to_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f876417a-a8f9-4b17-a409-8f5d57aca00e",
   "metadata": {},
   "source": [
    "### 参考文档\n",
    "《Python数据结构与算法分析（第2版）》：5.3.1 冒泡排序"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
